#include "LinkList.h"
#include <iostream>
#include "DynamicArray1.h"
LinkList::LinkList() : size(0)
{
    // 头结点：不放置有效数据，为了变成方便存在的结点
    head = new Node(0);
}

LinkList::~LinkList() // 从前往后释放，链表不能回头，头结点也要释放
{
    while (head != nullptr)
    {
        Node *nextNode = head->next; // 记下下一个结点
        delete head;
        head = nextNode; // 结点往后走
    }
}

void LinkList::InsertTail(const ElementType &element)
{
    // 遍历指针
    Node *travelPoint = head;
    while (travelPoint->next != nullptr)
        travelPoint = travelPoint->next;
    travelPoint->next = new Node(element); //()是初始化
    size++;
}

void LinkList::InsertHead(const ElementType &element) // O(1)
{
    Node *newNode = new Node(element);
    newNode->next = head->next;
    head->next = newNode;
    size++;
}

void LinkList::InsertByIndex(int index, const ElementType &element) // O(n)
{
    // 从头结点开始数index个，最终停在index-1个结点上
    Node *travelPoint = head;
    for (int i = 0; i < index; i++)
    {
        travelPoint = travelPoint->next;
    }
    Node *newNode = new Node(element);
    newNode->next = travelPoint->next;
    travelPoint->next = newNode;
}

void LinkList::RemoveByIndex(int index)
{
    if (index < 0 || index >= size)
    {
        std::cout << "非法删除位置!\n";
        return;
    }
    // 从头结点开始数index个，最终停在index-1个结点上
    Node *travelPoint = head;
    for (int i = 0; i < index; i++)
    {
        travelPoint = travelPoint->next;
    }
    Node *freeNode = travelPoint->next;
    travelPoint->next = freeNode->next;
    delete freeNode;
}

void LinkList::RemoveByElement(const ElementType &element)
{
    Node *travelPoint = head;
    while (travelPoint->next != nullptr)
    {
        if (travelPoint->next->data == element)
        {
            Node *freeNode = travelPoint->next;
            travelPoint->next = freeNode->next;
            delete freeNode;
            size--;
        }
        else
            travelPoint = travelPoint->next;
    }
}

LinkList::ElementType *LinkList::FindByIndex(int index)
{
    if (index < 0 || index >= size)
    {
        std::cout << "非法查找位置!\n";
        return nullptr;
    }
    Node *travelPoint = head;
    // 要找到index的位置，所以是i<=index
    for (int i = 0; i <= index; i++)
    {
        travelPoint = travelPoint->next;
    }
    return &travelPoint->data;
}

DynamicArray LinkList::FindByElement(const ElementType &element)
{
    DynamicArray result;
    Node *travelPoint = head->next;
    while (travelPoint != nullptr)
    {
        if (travelPoint->data == element)
        {
            result.InsertTail(&travelPoint->data);
        }
        travelPoint = travelPoint->next;
    }
    return result;
}

void LinkList::Reserve()
{
    Node *pre = nullptr;
    Node *current = head->next;
    Node *back = current->next;
    while (back != nullptr)
    {
        current->next = pre; // 逆序

        // 依次往后走
        pre = current;
        current = back;
        back = current->next;
    }
    current->next = pre;  // 最后一个结点的指针要单独逆序
    head->next = current; // 新的链表的头给到head的next
}

void LinkList::Reserve2()
{
    head->next = Reserve2(head->next);
}

void LinkList::BubbleSort()
{

    for (int i = 0; i < size - 1; i++)
    {
        Node *travelPoint = head; // 每一次都从头开始扫描链表
        for (int j = 0; j < size - i - 1; j++)
        {
            if (travelPoint->next->data > travelPoint->next->next->data)
            {
                Node *preNode = travelPoint->next; // 前面一个结点
                Node *backNode = preNode->next;    // 后一个结点
                preNode->next = backNode->next;
                backNode->next = preNode;
                travelPoint->next = backNode;
            }
            travelPoint = travelPoint->next;
        }
    }
}

void LinkList::Sort()
{
    FastSort(head->next, nullptr);
}

void LinkList::show()
{
    std::cout << "size:" << size << std::endl;
    // 遍历指针
    Node *travelPoint = head->next; // 头结点不需要输出
    while (travelPoint != nullptr)
    {
        std::cout << travelPoint->data << " ";
        travelPoint = travelPoint->next;
    }
    std::cout << std::endl;
}

// 双指针 : 快慢指针
void LinkList::FastSort(Node *start, Node *end)
{
    if (start == end)
        return;
    Node *temp = start;      // 基准值
    Node *slow = start;      // 慢指针
    Node *fast = slow->next; // 快指针
    while (fast != end)      // 不走到末尾
    {
        if (fast->data < temp->data)
        {
            slow = slow->next;
            std::swap(slow->data, fast->data); // 交换快慢指针的值
        }
        fast = fast->next;
    }
    std::swap(slow->data, temp->data); // 基准值归位
    // 递归
    FastSort(start, slow);
    FastSort(slow->next, end);
}

LinkList::Node *LinkList::Reserve2(Node *node)
{
    if (node->next == nullptr)
        return node; // 返回原来的尾巴，逆序之后链表的头
    else
    {
        Node *newHead = Reserve2(node->next); // 下一个结点递归到下一层
        node->next->next = node;              // 逆序
        node->next = nullptr; //新的最后一个结点的下一个指向nullptr
        return newHead; //把新的头层层返回
    }
    return nullptr;
}
